package main;

    /**
     * 快速排序：Java
     *
     * @author skywang
     * @date 2014/03/11
     */
    public class QuiteSort {
        /*
         * 快速排序
         *
         * 参数说明：
         *     a -- 待排序的数组
         *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
         *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
         */
        /*
         * 快速排序
         *
         * 参数说明：
         *     a -- 待排序的数组
         *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
         *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
         */
        static void quick_sort(int a[], int l, int r)
        {
            if (l < r)
            {
                int i,j,x;

                i = l;
                j = r;
                x = a[i];
                while (i < j)
                {
                    while(i < j && a[j] > x)
                        j--; // 从右向左找第一个小于x的数
                    if(i < j)
                        a[i++] = a[j];
                    while(i < j && a[i] < x)
                        i++; // 从左向右找第一个大于x的数
                    if(i < j)
                        a[j--] = a[i];
                }
                a[i] = x;
                quick_sort(a, l, i-1); /* 递归调用 */
                quick_sort(a, i+1, r); /* 递归调用 */
            }
        }


        public static void main(String[] args) {

            int [] a =  {30, 40, 60, 10, 20, 50};
            QuietSort(a,0,a.length-1);

            for (int i : a) {
                System.out.println(i);
            }
        }

        // 改进成方法

        public static  void QuietSort(int [] a, int l, int r  ){

            int left = l;
            int right = r;
            int cur = a[left];

            if( left < right){

                while ( left < right && a[right] > cur) {
                    right--;
                }
                if( left <  right){
                    a[left] =a[right];
                    // 之后从 左向 右 找 所以 left  需要++；
                    left++;
                }
                // 从右边找到 大于  基准数的
                while ( left< right && a[left] < cur ){
                    left++;
                }
                if( left < right){
                    a[right] = a[left];
                    right--;
                }

                a[left] = cur;
                // 递归

                QuietSort(a,l,left-1);
                QuietSort(a,left+1,r);
            }


        }

}
